# -*- coding: utf-8 -*-
'''
And now:
  Something completely diferent... The larch.
'''
import sys
import math
import time
import random

def max_heapify(A, i):
    global HEAPSIZE
    l = 2 * i
    r = l + 1
    
    if l <= HEAPSIZE and A[l] > A[i]:
        largest = l
    else:
        largest = i

    if r <= HEAPSIZE and A[r] > A[largest]:
        largest = r

    if largest != i:
        A[i], A[largest] = A[largest], A[i]
        max_heapify(A, largest)

def build_max_heap(A):
    global HEAPSIZE
    HEAPSIZE = len(A) - 1
    for i in range(int(math.floor(HEAPSIZE/2)), 0, -1):
        max_heapify(A, i)

def heapsort(A):
    global HEAPSIZE
    HEAPSIZE = len(A)-1
    build_max_heap(A)
    for i in range(len(A)-1, 1, -1):
        A[1], A[i] = A[i], A[1]
        HEAPSIZE = HEAPSIZE - 1
        max_heapify(A, 1)


def main():
    global HEAPSIZE 
    HEAPSIZE = 50000
    #HEAPSIZE = len(A) - 1
    #max_heapify(A, 2)
    #build_max_heap(A)
    for k in range(50000, 100000, 5000):
        A = [random.randint(0,1000) for k in range(0, k) ]
        A[0] = sys.maxint
        t1 = time.time()
        heapsort(A)
        t2 = time.time()
        print k, t2-t1
        A.pop(0)

main()

